This invention relates to database searching and queries, and more particularly to natural language based interactive database searching and queries in network environment.
Databases and database search techniques are very well known in the computer arts. Databases have various structures and include any given type of information. In many cases some or all of this information is retrieved by using one or more queries. A query is a request for information from the database that has a structure compatible with the database. Generally, the query is processed in a search that returns results to user.
One common technique for natural language access to databases is to convert natural language sentences to SQL statements. Some examples of SQL statements are shown below:
Query: Show me the names and batting averages of all players who batted above 0.250.
SELECT
Name, Average
FROM
Player
WHERE
Average greater than 0.250
Query: Show me the names and batting averages of all Oriole, Red Sox, and Expo players who batted above 0.300.
SELECT
Player.Name, Average
FROM
Player,Team
WHERE
Average greater than 0.300
AND
Player.Team=Team.Team
AND
Team.Name IN (xe2x80x98Oriolesxe2x80x99, xe2x80x98Red Soxxe2x80x99, xe2x80x98Exposxe2x80x99)
Query: Show me the sum of all batting averages of all players except these from the White Sox and Diamondbacks.
SELECT
SUM(Average)
FROM
Player,Team
WHERE
Player.Team=Team.Team
AND
Team.Name
NOT IN
(xe2x80x98White Soxxe2x80x99,xe2x80x98Diamondbacksxe2x80x99)
A paper titled xe2x80x9cNatural Language interfaces to databasesxe2x80x94an introductionxe2x80x9d by I. Androutsopoulos and G. D. Ritchie, appeared in Natural Language Engineering 1(1): 29-81; 1995 Cambridge University Press, which is herein incorporated by reference in its entirety, presents a history of natural language access to databases and provides a survey of the most significant problems that a program that provides such access must face. State-of-the-art database searching includes interactive search, natural language queries and search via internet. One non-natural language interactive database searching technique is described in U.S. Pat. No. 5,426,781 entitled xe2x80x9cComputerized report-based interactive database query interfacexe2x80x9d that discloses a method and system for interactively and iteratively constructing a query using a table metaphor displayed on a user display. Alterations are made directly to the table metaphor by the database user. The alterations relate to adding, deleting, or combining columns of attributes and limiting ranges of attribute values. The alterations are registered and the table metaphor updated to reflect the registered alterations. The table metaphor can be repeatedly used to further register additional alterations. The query corresponding to the table metaphor in its final form is run against the full database to generate a report in the format indicated by the table metaphor.
Using natural language queries to access the information system is also well known. U.S. Pat. No. 5,574,908 entitled xe2x80x9cMethod and apparatus for generating a query to an information system specified using natural language-like constructsxe2x80x9d (herein incorporated by reference in its entirety) discloses an apparatus for generating a query to an information system using a drag-and-drop information system specification means utilizing a computer language having both textual and graphical forms for translating natural language-like constructs into object-role modeling symbology.
Doing database searching over a general network, e.g. the internet, an intranet, etc. is also well known. In this type of database searching, one or more clients generate a query that is transmitted over the network, a process running on a search processes the query against one or more databases, and returns result to the client back over the network.
U.S. Pat. No. 5,737,592 entitled xe2x80x9cAccessing a relational database over the Internet using macro language filesxe2x80x9d (herein incorporated by reference in its entirety) discloses a method for executing Structured Query Language (SQL) queries in a computer-implemented relational database management system via a network.
One popular way of searching over a network (Internet) is to use a search engine. Most search engines are keyword based search such as YAHOO (http://www.yahoo.com), LYCOS (http://www.lycos.com) etc., where no user interaction is supported. The user is asked to input the keywords that best represent their interests, then the search engine will look for those keywords (and possibly the synonyms of those keywords) against the document collections. Where a match is found in the document, that document will be retrieved and presented to the user. A typical user is forced to manually go through the many xe2x80x9cmatchesxe2x80x9d for a query and find the relevant information herself.
Similar procedures are in place for searching for products. The customers either have to go through a possibly long series of clicking the hyperlinks, or use one of the search mechanisms described above.
Recently, some websites (www.AskJeeves.com, www.Neuromedia.com) have started search operations on question-answer mode. Natural language search engines, such as AskJeeves, use a relatively simple technical approach of keywords, and templates to give the user a feeling of a xe2x80x9cnatural language interfacexe2x80x9d. For example, a query xe2x80x9cWhat is the capital of Kenya?xe2x80x9d returns a pointer to several Web sites including one about Kenya where the correct answer is included in the text. However, a question xe2x80x9cHow long does it take to fly from London to Paris on the Concorde?xe2x80x9d produces a set of similar questions to the one asked however none of them is related to the answerxe2x80x94example: xe2x80x9cWhere can I find cheap flights from the UK?xe2x80x9d. The method used to produce answers seems to consist of a 5-steps: (a) partly parse the query; (b) map to a canned set of questions/question-templates; (c) map canned questions go to existing knowledge bases (AskJeeves points to other people""s web sites for the real data/FAQs.); (d) do a meta search on the 5 big search engines (and return their results too); and (e) if there was no match in xe2x80x9cbxe2x80x9d then record the query for later human analysis. Note that xe2x80x9cbxe2x80x9d is essentially a person-intensive task-creating the list of key phrases and the canned questions they map to (and then the underlying web pages they map to). Such systems provide a reasonable front end to a large knowledge base/FAQ. They are better than a raw search engine, because they have the human touch of mapping phrases to canned questions/templates (backed up with the search engines).
Other sites, such as Neuromedia (www.neuromedia.com), BigScience(www.bigscience.com), Novator(www.novator.com), PersonalLogic (www.personallogic.com) try to offer more interactivity to the user. By interactivity we mean the capability of a system to jointly define parameters required for mutual understanding in a series of exchanges. These might be some action parameters, such as Amount, Account_to, Account_from for transferring money, or a set of preferences for a computer notebook. These parameters may be established either by user providing information to the system or the system suggesting some or all of them. What is important is that the system remembers current (and possibly previous) user""s preferences, and is using this information in an intelligent manner to make the interaction more satisfying for the user. The above sites, offer more interactivity, by extending the question answer mode of operation with contextual history in the interaction.
The prior art systems fail primarily in three areas:
1. Efficiency: many rounds of interaction are needed to accomplish a task. A typical buying request on average takes about 20 mouse clicks.
2. Lack of deeper understanding of queries. Natural language engines such as AskJeeves cannot be used to accomplish transactions, such as buying clothes, because: (a) a keyword search cannot understand that xe2x80x9csummer dressxe2x80x9d should be looked upon in women""s clothing dept. under xe2x80x9cdressesxe2x80x9d and xe2x80x9cdress shirtxe2x80x9d most likely in men""s under xe2x80x9cshirtsxe2x80x9d, and (b) a search for xe2x80x9cshirtxe2x80x9d can reveal dozens or even hundred items, which is useless for somebody who has a specific style and pattern in mind. In order to have an appropriate answer, a dialogue with the user is required: the system must come back with questions, e.g., about style, color, etc.
3. Search engines do not accommodate business rules, e.g. a prohibition against displaying heap earrings with more expensive ones.
Search engines, such as AskJeeves, do not engage in dialog with the user, rather they respond to a single question with a set of possible answers. While these search engines are appropriate for searches and can be used in self service in many cases (e.g. For finding general information about the offerings of a bank), in order to have an exact answerxe2x80x94a dialog with the user is required and not sufficient in these systems. For example, to search for a xe2x80x9cshirtxe2x80x9d, sometimes, the user is aware of the specific style and can specify his/her exact interest right at the beginning in a sentence or two; sometimes, the user fails to input the crucial information for the specific style even if he/she has that in mind, sometimes, the user needs help to formulate his/her specific interest. Without dialog with the user to find out his/her exact intention and interest, the search result can reveal dozens or even hundreds of items which could be overwhelming and useless to the user.
For instance, trying to find a pair of black pants without cuffs might take over 10 minutes of exploration of a typical site (such as www.macys.com) because not all pants are available in blacks, some have cuffs and some do not, and also because it is not clear whether the search should be done under xe2x80x9ccareerxe2x80x9d, xe2x80x9ccasualxe2x80x9d or xe2x80x9cactivexe2x80x9d, if the pair in mind is xe2x80x9cbusiness casualxe2x80x9d.
Novator(www.novator.com), PersonalLogic (www.personallogic.com) try to offer more interactivity to the user, for instance in buying a computer a program could ask a number of questions to help with the configuration and pricing. However, the interaction is still unnatural and often time consuming for a casual user, because often it requires spending a lot of time either inputting information or browsing without any feedback from the system about getting closer to the user""s goal. Also, the user is required to use and understand the terminology of the site.
An object of this invention is an improved system, method, and program product for searching computer network sites.
An object of this invention is an improved system, method, and program product for searching computer network sites with fewer user requests to find a proper response to one or more queries.
An object of this invention is an improved system, method, and program product embodying a natural language dialog system that better analyzes and understands queries.
An object of this invention is an improved system, method, and program product embodying a natural language dialog system that allows for a dialog with a user.
An object of this invention is an improved system, method, and program product for searching computer network sites while accommodating domain rules, e.g. business rules.
This invention is a computer system, method, and program product that has a content database stored on one or more of its memories. The content database has a content organization that may or may not be part of the database. One or more presentation manager modules present information from the computer system to one or more users over one or more network interfaces and accept queries from one or more of the users using one or more known input/output modalities (e.g. Speech, typed in text, pointing devices, etc.). A natural language parser parses one or more natural language phrases received over one or more of the network interfaces by one or more of the presentation managers into one or more logical forms (parsed user input), each logical form having a grammatical and structural organization. A dialog manager module maintains and directs interactive sessions between each of the users and the computer system. The dialog manager receives logical forms from one or more of the presentation managers and sends these to a taxonomical mapping process which matches the items of interest to the user against the content organization in the content database to match business categories and sends modified logical forms back to the dialog manager. In a preferred embodiment, these modified logical forms are matched against a set of predefined action templates, the best matching template is selected, corresponding action requests are sent to an action manager, action results are received from the action manager, and presentation requests are sent to one or more of the presentation managers for presenting the system response to the user. The action manager module receives action requests from the dialog manager, executes the action (e.g. Retrieving the latest price of a stock or all blue pants with cuffs), and sends the action results to the dialog manager.